The interlace polynomial of a graph

Motivated by circle graphs, and the enumeration of Euler circuits, we define a one-variable “interlace polynomial” for any graph. The polynomial satisfies a beautiful and unexpected reduction relation, quite different from the cut and fuse reduction characterizing the Tutte polynomial.It emerges that the interlace graph polynomial may be viewed as a special case of the Martin polynomial of an isotropic system, which underlies its connections with the circuit partition polynomial and the Kauffman brackets of a link diagram. The graph polynomial, in addition to being perhaps more broadly accessible than the Martin polynomial for isotropic systems, also has a two-variable generalization that is unknown for the Martin polynomial. We consider extremal properties of the interlace polynomial, its values for various special graphs, and evaluations which relate to basic graph properties such as the component and independence numbers.     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

A Turán type inequality for rational functions with prescribed poles

Summary By employing a novel idea and simple techniques, we substantially generalize the Turán type inequality for rational functions with real zeros and prescribed poles established by Min [5] to include L^pspaces for 1≤p≤∞<span style='font-size:10.0pt'>while loosing the restriction ρ > 2 at the same time.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （PART I：EQUAL TIMES AND COSTS）

Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by realloeating resources. In this paper, authors consider a machine scheduling problemwith controllable processing times. In the first part of this paper, a special case where the pro-cessing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O（n^2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case, An effective heuristic to the genera/ problem will be presented.     

A DIRECT METHOD FOR THE UNIT CIRCLE PROBLEM

The unit circle problem is the problem of finding the number of eigenvalues of a non-Hermitian matrix inside and outside the unit circle . To reduce the cost of computing eigenvalues for the problem, a direct method, which is analogous to that given in [5], is proposed in this paper.     

Rational approximation in the complex plane using a τ-method and computer algebra

Numerous versions of the Lanczos τ-methods have been extensively used to produce polynomial approximations for functions verifying a linear differential equation with polynomial coefficients. In the case of an initial-value problem, an adapted τ-method based on Chebyshev series and the use of symbolic computation lead to a rational approximation of the solution on a region of the complex plane. Numerical examples show that the simplicity of the method does not prevent a high accuracy of results. This revised version was published online in June 2006 with corrections to the Cover Date.     

随机参数Duffing系统中的随机混沌及其延迟反馈控制

研究了谐和激励下含有界随机参数Duffing系统(简称随机Duffing系统)中的随机混沌及其延迟反馈控制问题.借助Gegenbauer多项式逼近理论，将随机Duffing系统转化为与其等效的确定性非线性系统.这样，随机Duffing系统在谐和激励下的混沌响应及其控制问题就可借等效的确定性非线性系统来研究.分析阐明了随机混沌的主要特点，并采用Wolf算法计算等效确定性非线性系统的最大Lyapunov指数，以判别随机Duffing系统的动力学行为.数值计算表明，恰当选取不同的反馈强度和延迟时间，可分别达到抑制或诱发系统混沌的目的，说明延迟反馈技术对随机混沌控制也是十分有效的. 关键词： 随机Duffing系统 延迟反馈控制 随机混沌 Gegenbauer多项式     

Lemniscates and inequalities for the logarithmic capacities of continua

It is shown that if P(z) = z ⁿ + ? is a polynomial with connected lemniscate E(P) = {z: ¦P(z)¦ ≤ 1} and m critical points, then, for any n? m+1 points on the lemniscate E(P), there exists a continuum γ ? E(P) of logarithmic capacity cap γ ≤ 2^?1/n which contains these points and all zeros and critical points of the polynomial. As corollaries, estimates for continua of minimum capacity containing given points are obtained.     

关于艾森斯坦因判别法的间接应用

探讨了间接应用艾森斯坦因判别法判断整系数多项式在有理数域上不可约的两种途径.     

Minimum concave cost production system: A further generalization of multi-echelon model

We will consider a concave minimization problem associated with a series production system in which raw material is processed inm consecutive facilities. The products at some facility are either sent to the next facility or stocked in the warehouse. The amount of demand for the final products during periodi, i = 1,,n, are known in advance. Our problem is to minimize the sum of processing, holding and backlogging cost, all of which are assumed to be concave.The origin of this model is the classical economic lot size problem of Wagner and Whitin and was extensively studied by Zangwill. This model is very important from the theoretical as well as practical point of view and this is one of the very rare instances in which polynomial time algorithm has been constructed for concave minimization problems.The purpose of this paper is to extend the model further to the situation in which time lag is associated with processing at each facility. We will propose an efficient O(n ⁴ m) algorithm for this class of problems.